# 在排序数组中查找元素的第一个和最后一个位置： https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/

class Solution:
    def searchRange(self, nums: list, target: int) -> list:
        """
            这种是判断mid 是否等于 target。不断收缩区间。
            还有一种思路解法是，不用判断mid 是否等于 target， 不断的收缩区间，去掉不包含target的区间
            最后left == right ，区间里还剩最后一个元素，判断他是否等于 target
        """
        left, right = 0, len(nums) - 1


        def getPos(nums, target, left, right, sign = 0):
            if not nums: return -1

            while left <= right:
                mid = (left + right + 1) // 2
                if nums[mid] < target:
                    left = mid + 1
                elif nums[mid] > target:
                    right = mid - 1
                elif nums[mid] == target:
                    if sign == 0:
                        # 如果mid 在数组开头下标0的位置，那么就是leftindex， 或者左边的元素小于target。
                        if mid == 0  or nums[mid - 1] < target:
                            return mid
                        # 否则因为是升序排列，说明左边的元素还有等于 target的， 那么缩小 right的范围，继续判断
                        right = mid - 1
                    else:
                        # 对右边的判断逻辑是一样的
                        if mid == len(nums) - 1 or nums[mid + 1] > target:
                            return mid
                        # 否则
                        left = mid + 1
            return -1
        
        leftIndex, rightIndex = getPos(nums, target, left, right), getPos(nums, target, left, right, 1)

        return [leftIndex, rightIndex]


# 还有一种思路解法是，不用判断mid 是否等于 target， 不断的收缩区间，去掉不包含target的区间
# 最后left == right ，区间里还剩最后一个元素，判断他是否等于 target
class Solution1:
    def searchRange(self, nums: list, target: int) -> list:
        """
            思路二：在循环体中排除一定不存在目标元素的区间
            这种在力扣执行时，用时更少一些
        """
        left, right = 0, len(nums) - 1


        def getPosRight(nums, target, left, right):
            if not nums: return -1

            while left < right:
                mid = left + ((right - left) + 1) // 2   # 注意这里的细节太难了， 要加1，mid向右靠
                if target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid
            return left if nums[left] == target else -1
        
        def getPosLeft(nums, target, left, right):
            if not nums: return -1

            while left < right:
                mid = left + ((right - left)) // 2   # 这里不用加1， mid向左靠。  这样才能挤出 left == right ,否则一直死循环
                if nums[mid] < target:
                    left = mid + 1
                else:
                    right = mid
            return left if nums[left] == target else -1
        
        leftIndex, rightIndex = getPosLeft(nums, target, left, right), getPosRight(nums, target, left, right)

        return [leftIndex, rightIndex]


nums = [5,7,7,8,8,10]
s = Solution1()
s.searchRange(nums, 6)